1. Field of the Invention
The present invention relates to a decoder for Reed-Solomon codes, an error position polynomial calculation method, and a program for executing the error position polynomial calculation method.
This application claims the priority of the Japanese Patent Application No. 2003-050327 filed on Feb. 27, 2003, the entirety of which is incorporated by reference herein.
2. Description of the Related Art
Reference Cited (Non-Patent Publication) 1:
Communications, 1998. ICC 98. Conference Record. 1998 IEEE International Conference on, Volume: 2, 1998, A (208,192;8) “Reed-Solomon decoder for DVD application” by: Rsie-Chia Chang; Shung, C. B., Page(s): 957–960 vol. 2.
Reference Cited (Non-Patent Publication) 2:
Communications, IEEE Transactions on, Volume: 47 Issue: 10, Oct. 1999, “On decoding of both errors and erasures of a Reed-Solomon code using an inverse-free Berlekamp-Massey algorithm” by: Jyh-Horng Jeng; Trieu-Kien Truong, Page(s): 1488–1494.
There has been a coding method of decoding Reed-Solomon codes. In this method, if positions of those received words that have dropped from a transmission path are given, more errors can be corrected based on data concerning the positions than errors corrected in normal corrections.
This method uses an erasure position polynomial which takes an erasure position as a solution thereof, in addition to a group of numerical values which is called a syndrome and is calculated and obtained from received words during normal decoding. It is hence possible to compensate for drops of data up to a number equal to the parity number at the maximum. When this method is used in combination with a so-called interleave method, it is possible to cope with drops of large received data which may depend on a damage on a recording medium.
A description will now be made along a decoding method for Reed-Solomon codes.
When corrections are normally made in Reed-Solomon decoding, the relationship of N−K=2t−1 exists between the maximum number t of correctible errors t and code parameters (N, K).
At first, a syndrome S0, S1, . . . , S2t−1 is calculated from received data by a syndrome calculation circuit.
The syndrome polynomial is expressed by the following expression (1).
                              S          ⁡                      (            x            )                          =                              ∑                          k              =              0                                                      2                ⁢                t                            -              1                                ⁢                                    S              k                        ⁢                          x              k                                                          (        1        )            
Also from the syndrome S0, S1, . . . , S2t−1, an error position polynomial is obtained by use of an error position polynomial calculation circuit. The error position polynomial is a polynomial expressed by the following expression (2) where positions of errors are Z0, Z1, . . . , Z2t−1.
                              σ          ⁡                      (            x            )                          =                                            ∏                              k                =                0                                                              2                  ⁢                  t                                -                1                                      ⁢                          (                              1                -                                                      Z                    k                                    ⁢                  x                                            )                                =                                    ∑                              i                =                0                                                              2                  ⁢                  t                                -                1                                      ⁢                                          σ                i                            ⁢                              x                i                                                                        (        2        )            
Further, an error value polynomial Ω(x) is obtained by the following expression (3) from the error position polynomial σ(x) and the syndrome.Ω(x)=S(x)σ(x)mod x2t  (3)
Hence, the position and numerical value of an actual error can be derived from these expressions.
To construct a circuit for decoding Reed-Solomon codes, the circuit which derives the error position polynomial σ(x) makes the greatest influences on the circuit scale and the number of operation steps. The foregoing cited reference 1 introduces a circuit equipped with Berlekamp algorithms, as the circuit which calculates the error position polynomial σ(x). This circuit is shown in FIG. 1.
Provided in the circuit shown in FIG. 1 are input registers rg14 for the syndrome S0, S1, . . . S2t−1 and a selector SEL14 for making a selection from the input registers rg14. Also provided are a shift register SR1 for the series of variable σ and a shift register SR2 for the series of valuable λ. There are further provided adders AD11 and AD12, multipliers ML11, ML12, and ML 13, registers rg11, rg12, and rg13, and selectors SEL11 and SEL12.
In case of this circuit, a Galois field operation circuit having a large scale is constructed from only three circuits (multipliers ML11, ML12, and ML13), which is superior from the viewpoint of the circuit scale. This circuit, however, does not support erasure corrections.
When an erasure position expressed in form of a Galois field which indicates an error position of a symbol among code words is obtained in advance in correction processing for Reed-Solomon codes, the number of correctible errors can be raised up to N−K. This is called an erasure correction. The number of erasure position codes, Neras (the number of erasure errors), and Nerr (the number of errors) have the following relationship (4) between each other.N−K=Neras+2Nerr  (4)
To make only erasure corrections, at first, the erasure position polynomial Λ(x) expressed by the following expression (5) is calculated from a Galois field expressing an erasure position.
                              Λ          ⁡                      (            x            )                          =                                            ∏                              k                ∈                                  {                  erasure_location                  }                                                      ⁢                          (                              1                -                                                      ⅇ                    k                                    ·                  x                                            )                                =                                    ∏                              i                =                0                                                              2                  ⁢                  t                                -                1                                      ⁢                                          Λ                i                            ⁢                              x                i                                                                        (        5        )            
To make only erasure corrections, the error value polynomial may be derived by substituting this expression for σ(x) in the foregoing expression (2).
In case of performing simultaneously both the normal error corrections and the erasure corrections, the error position polynomial σ is derived from the syndrome and the erasure position polynomial Λ.
The other foregoing cited reference 2 proposes modified Berlekamp algorithms which can perform erasure corrections with less changes to conventional algorithms.
FIG. 2 shows the entire configuration of a decoder proposed in the cited reference 2 in case of performing the normal error corrections and the erasure corrections simultaneously.
A syndrome calculator 31 calculates the syndrome S0, S1, . . . , S2t−1 from inputted data c.
An erasure position polynomial calculator 32 obtains the erasure position polynomial Λ(x) from erasure flags e0, e1, . . . , e2t−1 by the foregoing expression (5).
An error position polynomial calculator 33 derives an error position polynomial σ(x) from the syndrome S0, S1, . . . , S2t−1 and the erasure position polynomial Λ(x).
A Chien searcher 35 obtains a numerical error value from the error position polynomial σ and the error value polynomial 106 (x). Further, inputted data c is delayed by a delay buffer 36 to predetermined timing and inputted to an operator 37. In this operator 37, the inputted data c is subjected to an operation using the numerical error value from the Chien searcher 35, and is outputted as decoded data c′.
This configuration performs the normal error corrections and the erasure corrections simultaneously. It is however necessary for this configuration to derive the erasure position polynomial Λ(x) from the erasure flags e0, e1, . . . , e2t−1 before deriving the error position polynomial σ(x). In addition, the erasure position polynomial Λ(x) must be processed after the syndrome calculation because the erasure position polynomial Λ(x) cannot be calculated before all the erasure flags are inputted. Therefore, if the configuration shown in FIG. 2 is adopted, an operation step of calculating the erasure position polynomial is needed after completion of the syndrome calculation. A problem hence arises in that the number of necessary operation steps increases.